/*  This is a modified version of the finite state machine from an ECE 485 assignment.  It models the Least Recently Used
logic of a 4-way set associative cache to determine what the order of access is in relation to the ways of a set, and
what the current least recently used way is, for purposes of eviction.

The inputs are:

access - When access goes high, the module assumes that an access is being made to the cache, and loads in the current
state bits from the cache set being accessed.  Depending on which line, or way, is being accessed, the module sets and
clears the appropriate bits in the current state, and loads them into the next state output register.  The process that
is activated by access going high also evaluates the new next state to determine what the current Least Recently Used
line or way is, and loads a 4-bit, one-hot encoded number representing that line into the LRU output register.

line - This is a 4-bit number that passes the information from the cache concerning which line or way from the set is
being accessed during this cycle.  In the next level up where this module is being implemented, the line bits
must be set before access is asserted, or else the output data will be invalid.

curstate - This is a 6-bit number that passes the current state from the cache to this module.  The current state is the
set of bits b(i,j) such that b = 1 if i>j or 0 if i<j.  For a 4-way cache 6 bits are needed, and the order of the bits
in curstate is (0,1) (0,2) (0,3) (1,2) (1,3) (2,3).

The outputs are:

data_valid - This is a single bit flag that is asserted when the nextstate and LRU output data are valid, i.e. not in the
process of being determined in the case statements.  When the case statement starts after access is asserted, the data_valid
output goes to 0, and is set back to 1 when the case statements are done.

nextstate - This is a 6-bit number that passes the new state from this module back to the cache.  It is the same data that
is passed in as curstate, but modified by setting or clearing the appropriate bits for the access that was made during this
cycle.  When data_valid is equal to 1, the data on this output is assumed to be valid and current for the set that it was
calculated for.

LRU - This is a 2-bit number that indicates which way or line in the set currently being accessed is the least recently used.  
Binary 0 corresponds to way 0, 1 to way 1, 2 to way 2, and 3 to way 3.  When data_valid is equal to 1, the data on this output 
is assumed to be valid and current for the set that it was calculated for. */

module 4way_LRU (access, line, curstate, data_valid, nextstate, LRU);

input access;
input [3:0] line;
input [5:0] curstate;
output [5:0] nextstate;
output [1:0] LRU;
output data_valid;

reg b0_1, b0_2, b0_3, b1_2, b1_3, b2_3;  //These are the individual registers containing bits b(i,j).  These are set each access
					 //from curstate, and at the end of each access they are copied into nextstate for output.
reg [1:0] LRU;
reg [5:0] nextstate;
reg data_valid;

initial
begin
  {b0_1, b0_2, b0_3, b1_2, b1_3, b2_3} = 6'bxxxxxx;
  data_valid = 1'b0;
  LRU = 2'bxx;
  nextstate = 6'bxxxxxx;
end

always @ (posedge access)  //This is the routine that is started with each access.
begin
    
    data_valid = 1'b0; // First, the data_valid flag is set to 0.
    {b0_1, b0_2, b0_3, b1_2, b1_3, b2_3} = curstate;  //Then, the bits b(i,j) are copied in from curstate.
    LRU = 2'bxx;  //LRU is set to don't care until it is recalculated.
   
    casex ( {line[3], line[2], line[1], line[0]} )  // The case statement evaluated which way or line is being accessed.
    
    default : ; //If any other combination besides the four corresponding to an access of
    		//a single line is found, do nothing, as it is assumed to be erroneous input.

    4'b0000 : ; //If none of the line bits are set, do nothing, since this is invalid data.
      
    4'b0001 :  //Line 0 is being accessed.
    begin
      b0_1 = 1'b1; //Here the appropriate bits b(i,j) for this line are set or cleared
      b0_2 = 1'b1; //so that they reflect the access.  In this case, line 0 is now more recently
      b0_3 = 1'b1; //used that lines 1, 2 or 3, so b(0,1), b(0,2) and b(0,3) are all set.
    end
    
    4'b0010 :  //Line 1 is being accessed
    begin
      b1_2 = 1'b1;
      b1_3 = 1'b1;
      b0_1 = 1'b0;
    end
    
    4'b0100 :  //Line 2 is being accessed
    begin
      b0_2 = 1'b0;
      b1_2 = 1'b0;
      b2_3 = 1'b1;
    end
    
    4'b1000 :  //Line 3 is being accessed
    begin
      b0_3 = 1'b0;
      b1_3 = 1'b0;
      b2_3 = 1'b0;
    end
    
    endcase

    nextstate = {b0_1, b0_2, b0_3, b1_2, b1_3, b2_3}; //The modified bits are placed into the nextstate output
						      //register.
    
    casex ( {b0_1, b0_2, b0_3, b1_2, b1_3, b2_3} )  //The new state is evaluated to determine the new least recently
						    //used way or line.
    
      default : ; //do nothing if none of the conditions applies
      6'b000xxx: LRU = 2'b00; //line 0 is the LRU
      6'b1xx00x: LRU = 2'b01; //line 1 is the LRU
      6'bx1x1x0: LRU = 2'b10; //line 2 is the LRU
      6'bxx1x11: LRU = 2'b11; //line 3 is the LRU
     
    endcase
    
    data_valid = 1'b1; //Now that the new state and the LRU have been determined, data valid is set back to 1 to
		       //indicate that the data in these outputs is current and correct.
  
end

endmodule

